'''Project Euler Problem # 15:
Starting in the top left corner of a 2x2 grid, there are 6 routes (without
backtracking) to the bottom right corner.

How many routes are there through a 20x20 grid?'''

answer = 0
gridsize = 20

'''def dec2bin(n):
    'convert denary integer n to binary string bStr'
    bStr = ''
    if n < 0:  raise ValueError, "must be a positive integer"
    if n == 0: return '0'
    while n > 0:
        bStr = str(n % 2) + bStr
        n = n >> 1
    return bStr

print 'checking paths from 0 to %i' % (2**gridsize * 2)
for path in range(2**gridsize * 2):
    print 'checking path %i' % path
    pathstop = 0
    for bit in range(gridsize * 2 - 1):
        if (1 << bit) & path:
            pathstop += 1
    if pathstop == gridsize:
        answer += 1
        print dec2bin(path)
    
answer *= 2'''

def diagPermute(n):
    permute = [1]
    while len(permute) <= n:
        permute = map(lambda x,y:x+y , permute+[0],[0]+permute)
    return permute
    
def pe015(gridsize): 
    return sum([point**2 for point in diagPermute(gridsize)])

print 'The answer to Problem #15 is >> %i <<' % pe015(gridsize)